package com.dy.分类.图._210课程表二;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class GraphNode{
    int course;
    int degree;
    ArrayList<GraphNode> neighbors;

    public GraphNode(int course) {
        this.course = course;
        this.degree=0;
        neighbors = new ArrayList<>();
    }
}
public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int res[] = new int[numCourses];
        ArrayList<GraphNode> nodes = new ArrayList<>();
        //初始化节点
        for(int i=0;i<numCourses;i++){
            nodes.add(new GraphNode(i));
        }
        //初始化边,第二个点指向第一个点
        for(int i=0;i<prerequisites.length;i++){
            GraphNode begin = nodes.get(prerequisites[i][0]);
            GraphNode end = nodes.get(prerequisites[i][1]);
            end.neighbors.add(begin);
            begin.degree++;
        }
        Queue<GraphNode> q = new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            GraphNode node = nodes.get(i);
            if (node.degree==0) {
                q.add(node);
            }
        }
        int j=0;
        while(!q.isEmpty()){
            GraphNode node = q.poll();
            res[j++] = node.course;
            for(int i=0;i<node.neighbors.size();i++){
                GraphNode neighbor = node.neighbors.get(i);
                neighbor.degree--;
                if(neighbor.degree==0){
                    q.add(neighbor);
                }
            }
        }
        for(int i=0;i<numCourses;i++){
            if(nodes.get(i).degree!=0){
                return new int[]{};
            }
        }
        return res;
    }
}
